package week_04;

import javax.swing.*;
import java.util.ArrayList;
import java.util.List;

/**
 * 实现小根二叉堆
 * 实现方法
 * pop(): 弹出堆顶
 * insert(): 加入元素
 * delete(ListNode node): 删除任意节点元素
 * <p>
 * 基础操作--调整节点位置：
 * heapifyDown(): 向下调整位置
 * heapifyUp(): 向上调整位置
 */
public class BinaryHeap {
    List<ListNode> heap;

    public BinaryHeap() {
        heap = new ArrayList<>();
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }

    public ListNode pop() {
        ListNode top = heap.get(0);
        //尾节点替换到堆顶
        heap.set(0, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
        //再向下调整
        heapifyDown(0);
        return top;
    }

    public void push(ListNode node) {
        heap.add(node);
        heapifyUp(heap.size() - 1);
    }

    private void heapifyUp(int child) {
        // 一路向上跟父节点比较，直到满足堆性质，小于父节点停止
        while (child > 0) {
            int parent = (child - 1) / 2;
            if (heap.get(child).val < heap.get(parent).val) {
                swap(parent, child);
            } else {
                break;
            }
            child = parent;
        }
    }

    private void heapifyDown(int p) {
        // 跟左右节点比较 找到下一个child
        // 调整知道满足堆特性
        int child = p * 2 + 1;
        while (child < heap.size()) {
            int anotherChild = p * 2 + 2;
            if (anotherChild < heap.size() &&
                    heap.get(anotherChild).val < heap.get(child).val) child = anotherChild;
            if (heap.get(child).val < heap.get(p).val) {
                swap(p, child);
            } else {
                break;
            }
            p = child;
            child = p * 2 + 1;
        }
    }

    public void swap(int i, int j) {
        ListNode tmp = heap.get(j);
        heap.set(j, heap.get(i));
        heap.set(i, tmp);
    }


}
